A graph has a number of vertices interconnected through edges. Graphs are used to model a wide variety of systems and, consequently, have wide application. For example, one application of a graph is to describe computers and their interconnections on a computer network. Once a graph is used to describe a system, graph analysis may be performed to analyze the graph. Graph analysis is fundamental to many applications in computing, such as determining routing and layout in computer networks, determining routing and layout in very large scale integrated (VLSI) circuit computer-aided drafting (CAD), and determining relationships in computer graphics.
One conventional graph analysis method determines whether a destination vertex may be reached if one starts at a source vertex. This is called “reachability.” Another conventional graph analysis method can determine one or more shortest paths between a source vertex and a destination vertex. This method is appropriately called “shortest path determination.” The shortest path determination may also include determining reachability.
Software implementations of graph analysis methods usually involve “walking” the graph by following chains of pointers, or by repeatedly indexing into a two-dimensional array containing an adjacency matrix for the graph. The adjacency matrix is one technique used to describe the graph. A limiting factor for the performance of such software implementations is memory latency. Memory latency is recognized by the computer architecture community to be a major bottleneck that will become increasingly severe, particularly as processor speeds continue to increase faster than memory performance. See, for instance, Wulf et al., “Hitting the Memory Wall: Implications of the Obvious,” Computer Architecture News, 23(1):20-24 (1995), the disclosure of which is hereby incorporated by reference.
The non-local and irregular memory accesses implied by following chains of pointers further diminish the effectiveness of caches introduced to mitigate processor and memory speed imbalance. This tends to slow memory accesses and, consequently, graph analysis. Furthermore, large graphs, such as graphs having thousands or tens of thousands of vertices, can use copious amounts of memory, processing power, and time for software implementations of graph analysis.
A need therefore exists for techniques that provide efficient graph analysis yet allow large graphs to be analyzed.